package com.bigshen.algorithm.nUnionFind.solution02NumberOfIslandsII;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

/**
 * 小岛问题
 * 一座 m * n 的海水区域，随机放入N个坐标来表示小岛， 没放入一个，求出小岛个数，相邻小岛算作一座小岛
 *
 */
public class NumberOfIslandII {

     class UnionFind {
         // 保存父子关系， key为child : value为parent
         Map<Integer, Integer> parentMap = new HashMap();

         public UnionFind(int m, int n) {
             // 初始化父子节点
             for (int i = 0; i < m ; i ++) {
                 for (int j = 0; j < n; j ++) {
                     int id = convertId(i, j, m);
                     parentMap.put(id, id);
                 }
             }
         }

         public Integer convertId(int x, int y, int m) {
             // 将坐标转换为唯一id
             return x*m + y;
         }

         public Integer find(int x) {
             // 找到祖父节点
             Integer root = parentMap.get(x);
             while (root != parentMap.get(root)) {
                 // 如果当前节点的父节点不是它自己，说明没到根节点
                 root = parentMap.get(root);
             }

             // 子孙节点升级
             int tmp = -1;
             int fat = x;
             while (fat != parentMap.get(fat)) {
                 tmp = parentMap.get(fat);
                 parentMap.put(fat, root);
                 fat = tmp;
             }

             return root;
         }

         // 祖父节点合并
         public void union(int x, int y) {
             int fa_x = parentMap.get(x);
             int fa_y = parentMap.get(y);
             if (fa_x != fa_y) {
                 parentMap.put(fa_x, fa_y);
             }
         }

     }

    // 放入N个节点，依次返回放入节点后小岛个数
    // 借助并查集UnionFind来标记节点是否有共同祖先节点，有共同节点的为同一座岛屿
    public List<Integer> countIslands(int m, int n, Point[] points) {
         List<Integer> result = new ArrayList<>();
        if (m < 1 || n < 1 || null == points || points.length < 1) {
            return result;
        }

        //岛屿数量
        int total = 0;
        // 兄弟节点坐标
        int[] xArray = {1, -1, 0, 0};
        int[] yArray = {0, 0, 1, -1};
        // 节点是否为小岛
        boolean[][] visited = new boolean[m][n];
        // unionFind初始化
        UnionFind union = new UnionFind(m, n);
        for (int i = 0; i < points.length; i ++) {
            Point point = points[i];
            int x = point.x;
            int y = point.y;
            visited[x][y] = true;
            total ++;
            for (int j = 0; j < 4; j ++) {
                int xBrother = x + xArray[j];
                int yBrother = y + yArray[j];
                // 找到兄弟节点，如果兄弟节点为岛屿，则小岛合并
                if (xBrother > -1 && yBrother >-1 && xBrother < m && yBrother < n
                        && visited[xBrother][yBrother]) {
                    int id = union.convertId(x, y, m);
                    int brotherId = union.convertId(xBrother, yBrother, m);
                    int faId = union.find(id);
                    int faBrotherId = union.find(brotherId);
                    if (faId != faBrotherId) {
                        // 新插入的节点和兄弟节点相连，本为一座岛屿，合并
                        union.union(faId, faBrotherId);
                        // 岛屿合并，数量相减
                        total --;
                    }
                }
            }
            result.add(total);
        }
        return result;
    }

    public static void main(String[] args) {

         NumberOfIslandII numberOfIslandII = new NumberOfIslandII();

//         Point p1 = new Point(1, 1);
//         Point p2 = new Point(1, 3);
//         Point p3 = new Point(1, 5);
//         Point p4 = new Point(1, 2);
//         Point p5 = new Point(1, 4);
        Point p1 = new Point(1,1);
        Point p2 = new Point(1,3);
        Point p3 = new Point(1,2);
        Point p4 = new Point(3,1);
        Point p5 = new Point(3,3);
        Point p6 = new Point(3,2);
        Point p7 = new Point(2,2);
        Point[] points = {p1, p2, p3, p4, p5, p6, p7};
         List<Integer> islands = numberOfIslandII.countIslands(5, 6, points);

         for (int i = 0; i < islands.size(); i ++) {
             System.out.println(islands.get(i));
         }

    }

}

class Point {

    int x;
    int y;

    public Point(int a, int b) {
        x = a;
        y = b;
    }

}
